/*
 * @Author: szx
 * @Date: 2021-11-09 13:24:31
 * @LastEditTime: 2021-11-09 13:42:59
 * @Description:
 * @FilePath: \leetcode\600-699\653\653.cpp
 */
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right)
        : val(x), left(left), right(right) {}
};

class Solution {
   public:
    bool findTarget(TreeNode *root, int k) {
        vector<int> vec;
        zhongxu(root, vec);
        for (int i : vec) {
            cout << i << " ";
        }
        cout << endl;
        int l = 0, r = vec.size()-1;
        int sum = 0;
        while (l < r) {
            sum = vec[l] + vec[r];
            if (sum == k) {
                return true;
            }
            if (sum > k)
                r--;
            else
                l++;
        }
        return false;
    }
    void zhongxu(TreeNode *root, vector<int>& vec) {
        if (!root) return;
        zhongxu(root->left, vec);
        vec.push_back(root->val);
        zhongxu(root->right, vec);
    }
};